As is well known in the art, search engines can store a number of values, each of which may represent one entry. A comparand value (or key) may be compared to data values in such entries. The relative rapid speed at which content addressable memories (CAMs) can compare multiple entries to an applied comparand value, as compared to software or other approaches, has resulted in CAMs enjoying widespread use in higher speed applications, such as packet processing.
Conventional CAMs may include binary CAMs and ternary CAMs. Binary CAMs typically include entries that can each store a data value having a number of data bits. In most cases, a match indication can be generated when all bits of a comparand value match all the bits of an entry. CAMs may also include ternary CAMs. Ternary CAMs may typically include entries having data bits, some or all of which may be masked from a compare operation.
A conventional ternary CAM will be briefly described. Referring now to FIG. 13, a portion of a conventional ternary CAM array is set forth in a block diagram and designated by the general reference character 1300. A conventional ternary array 1300 may include a number of CAM cells 1302(m,n), where m can indicate a particular array row position and n can indicate a particular array column position. Each CAM cell 1302(m,n) can be connected one or more compare lines and a match line.
In the example of FIG. 13, CAM cells 1302(m,n) of the same column can be connected to the same complementary compare lines 1304-m. Each pair of complementary compare lines 1304-n may carry a comparand value that can be compared to a data value stored within a CAM cell 1302(m,n). CAM cells 1302(m,n) of the same row may be connected to the same match line 1306-n. In a typical arrangement, CAM cells 1302(m,n) of the same row may store data bit values for one entry.
Referring now to FIG. 14, a conventional example of a ternary cell is shown in a block diagram and designated by the general reference character 1400. A conventional ternary CAM cell 1400 may include a data store 1402 that may store a data bit value, a mask store 1404 that may store a mask value, and a compare circuit 1406. A compare circuit 1406 can receive a data value, mask value, and comparand value to perform a match operation. While data and mask stores may take various forms, typically some sort of flip-flop type circuit such as a conventional static random access memory (SRAM) type cell, can be used as a data and/or mask store. Similarly, a compare circuit may take a variety of forms, but usually includes an exclusive-OR (XOR) or exclusive-NOR (XNOR) type circuit.
One example of a compare circuit, such as that shown as 1406, is shown in a schematic diagram in FIG. 15. The compare circuit is designated by the general reference character 1500 and may be connected between a match line 1502 and a first potential, VSS. Parallel paths 1504-0 and 1504-1 may be formed between the first potential VSS and a compare node 1506. In addition, a mask circuit 1508 may be formed between the compare node 1506 and the match line 1502. A path 1504-0 may receive a compare value C and an inverse data value D_. Similarly, a path 1504-1 may receive an inverse compare value C_ and a data value D. Thus, when a compare value C does not match a data value D, the paths (1504-0 and 1504-1) may be enabled (i.e., have a low impedance), connecting (discharging) the compare node 1506 to the first potential VSS. In contrast, when a compare value C matches a data value D, the paths are disabled (i.e., have a high impedance), isolating compare node 1506 from the first potential VSS.
A mask circuit 1508 may receive a mask value M_. If a mask value is active (low in this case), a mask circuit 1508 may isolate a match line 1502 from a compare node 1506. Thus, regardless of whether a match exists between a compare value C and a data value D, a match line 1502 may remain isolated from the first potential VSS. Conversely, if a mask value is inactive (high in this case) a mask circuit 1508 may connect a match line 1502 to a compare node 1506. In such a configuration, a match line 1502 may be connected to or isolated from a first potential VSS according to a match/mis-match between a data value D and a compare value C.
In this way, ternary CAMs may provide maskable compare operations.
Various CAM applications can include a variety of types of matching operations. At one end of the spectrum are “exact” match operations, such as those that may be provided by a CAM. However, other applications may include more complicated match operations. For example, in some cases it may be desirable to determine if a given comparand value, or portion thereof, falls within a given range.
Ternary CAMs may provide limited range matching by masking out consecutive bits of lower significance of an entry value. Such an approach may require multiple entries in the event a given matching range does not fall along a bit value boundary. As but one example, an entry 1111 XXXX (where X represents a masked bit) may be used to match a range from 255 (1111 1111) to 240 (1111 0000). However, multiple entries may be needed to match a different range, such as 255 to 246. Such multiple entries may consume too much of the available CAM entry space.
Alternative conventional approaches to providing range matching can include a processor-oriented approach. Such an approach may store upper and lower values of a range. Such values may be compared to a comparand value according to some sort of algorithm to thereby determine if a range match has occurred. Such an approach may take multiple processor cycles, thus consuming more time than a typical CAM match operation.
While various conventional approaches to range matching exist, there remains a need to improve the speed at which range matching can be performed. In addition, or alternatively, there is a need for a range matching solution that does not consume multiple entries, as in the case of some conventional ternary CAM solutions.